A solid state drive (SSD) is a data storage device that utilizes solid-state memory to retain data in nonvolatile memory chips. NAND-based flash memories are widely used as the solid-state memory storage in SSDs due to their compactness, low power consumption, low cost, high data throughput and reliability. SSDs commonly employ several NAND-based flash memory chips and a flash controller to manage the flash memory and to transfer data between the flash memory and a host computer.
While NAND-based flash memories are reliable, they are not inherently error-free and often rely on error correction coding (ECC) to correct raw bit errors in the stored data. One commonly employed error correction code employed in nonvolatile memory storage modules, such as SSDs, are low-density parity-check (LDPC) codes. An LDPC code is a linear error correcting code having a parity check matrix with a small number of nonzero elements in each row and column.
Various methods for decoding data encoded with LDPC error correction codes are known in the art, including the sum-product algorithm (SPA) and the min-sum algorithm (MSA). While the sum-product algorithm (SPA) is known to achieve the best decoding performance, it is computationally complex. The min-sum algorithm (MSA) was introduced to reduce the computationally complexity inherent in the sum-product algorithm. Additionally, one commonly employed decoding method for LDPC coding, comprising a further hardware simplification, is the layered min-sum algorithm (MSA). The layered min-sum algorithm is iterative by layer of the parity check matrix.
While the layered min-sum algorithm performs very well utilizing layered iterative decoding based on belief propagation, the combination of the structure of the parity check matrix used for the encoding of the data and the decoding process itself may result in the undesirable creation of error mechanisms, such as trapping sets and stopping sets during the iterative decoding process. These undesirable error mechanisms may force the decoder to converge to an incorrect result, leading to undesired retransmission of the frame or undesired noise at the receiver.
Accordingly, what is needed in the art is an improved system and method for reducing the effect of error mechanisms, such as trapping sets and stopping sets, on a belief propagation algorithm for decoding LDPC encoded data.